Aiming at the capacity P-median problem of continuous domains under the dense demand, the Centroidal Capacity Constrained Power Diagram (CCCPD) theory was proposed to approximately model the continuous P-median problem and accelerate the solving process. The Power diagram was constructed by extended Balzer's method, centroid restriction was imposed to satisfy the requirements of P-median, and capacity constraint was imposed to meet the capacity requirements of certain demand densities. The experimental results show that the proposed algorithm can quickly obtain an approximate feasible solution, having the advantages of better computing efficiency and capacity accuracy compared to Alper Murata's method and Centroidal Capacity Constrained Voronoi Tessellation (CCCVT) respectively. Additionally, the proposed method has excellent adaptability to complex density functions.
Concerning the application requirements for the fast classification of large-scale remote sensing images, a parallel classification method based on K-means algorithm was proposed. Combined the CPU process-level and thread-level parallelism features, reasonable strategies of data granularity decomposition and task scheduling between processes and threads were implemented. This algorithm can achieve satisfactory parallel acceleration while ensuring classification accuracy. The experimental results using large-volume and multi-scale remote sensing images show that: the proposed parallel algorithm can significantly reduce the classification time, get good speedup with the maximum value of 13.83, and obtain good load-balancing. Thus it can solve the remote sensing image classification problems of the large area.
Methods of parallel computation are used in validating topology of polygons stored in simple feature model. This paper designed and implemented a parallel algorithm of validating topology of polygons stored in simple feature model. The algorithm changed the master-slave strategy based on characteristics of topology validation and generated threads in master processor to implement task parallelism. Running time of computing and writing topology errors was hidden in this way. MPI and PThread were used to achieve the combination of processes and threads. The land use data of 5 cities in Jiangsu, China, was used to check the performance of this algorithm. After testing, this parallel algorithm is able to validate topology of massive polygons stored in simple feature model correctly and efficiently. Compared with master-slave strategy, the speedup of this algorithm increases by 20%.